package com.gorkr.labuladong.data_struct.array;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author gorkr
 * @date 2022/08/07 19:12
 **/
public class M38ZiFuChuanDePaiLieIcof {

    private StringBuilder sb = new StringBuilder();
//    List<String> res = new LinkedList<>();
    HashSet<String> res = new HashSet<>();

    public String[] permutation(String s) {
//        HashSet<Character> hashSet = new HashSet<>();
//        for (int i = 0; i < s.length(); i++) {
//            hashSet.add(s.charAt(i));
//        }
//        char[] chars = hashSet.stream().map(Character::charValue).toArray();
//       Character[] chars = hashSet.stream().map(character -> character).collect()
//           Character[] chars = new Character[hashSet.size()];
//        hashSet.toArray(chars);
        char[] chars = s.toCharArray();
        Arrays.sort(chars);

        boolean[] visited = new boolean[chars.length];
        traverse(chars,visited,0);

        return res.toArray(new String[0]);

    }

    private void traverse(char[] chars, boolean[] visited, int times) {

        // basecase
        if (times >= chars.length) {
            res.add(new String(sb));

            return;
        }

        for (int i = 0; i < chars.length; i++) {

            if(visited[i]){
                // 已经被访问过
                continue;
            }
//            if(i>0&&chars[i-1]==chars[i]){
//                continue;
//            }

            visited[i] = true;
            sb.append(chars[i]);
            traverse(chars,visited,++times);
            --times;
            visited[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }

    @Test
    public void test() {
        String[] abcs = permutation("aab");
        for (String s: abcs
        ) {
            System.out.println(s);
        }

    }

}
    